package examination;

/**
 * Created by zxc on 2018/9/16.
 * 动态规划：击鼓传花
 * 设有N个人围成一个圈，每人手里都握着一个令牌写明一个数字（随机生成的）。从第一个人开始玩“击鼓传花”游戏，
 第一个击的次数为其令牌上写明的数字数（假设为m1）。第m1个人出列。下次再从第m1+1个人开始新的“击鼓传花”
 击的次数也为其令牌上写明的次数，等于该次数的人出列。直到剩下最后一个人。
 * https://www.cnblogs.com/smyhvae/p/4768538.html
 */

public class Drhat {
    //结点类
    class Node {
        Object element; //数据域
        Node next;  //指针域

        //头结点的构造方法
        public Node(Node nextval) {
            this.next = nextval;
        }
        //非头结点的构造方法
        public Node(Object obj, Node nextval) {
            this.element = obj;
            this.next = nextval;
        }

        //获得当前结点的指针域
        public Node getNext() {
            return this.next;
        }
        //获得当前结点数据域的值
        public Object getElement() {
            return this.element;
        }
        //设置当前结点的指针域
        public void setNext(Node nextval) {
            this.next = nextval;
        }
        //设置当前结点数据域的值
        public void setElement(Object obj) {
            this.element = obj;
        }
        public String toString() {
            return this.element.toString();
        }
    }



    //单向循环链表类
    public static class CycleLinkList {

        Node head; //头指针
        Node current;//当前结点对象
        int size;//结点个数

        //初始化一个空链表
        public CycleLinkList()
        {
            //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
            /*this.head = current = new Node(null);*/
            this.size =0;//单向链表，初始长度为零。
            this.head.next = this.head;
        }

        //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。
        //比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点，然后修改a1节点的指针域
        public void index(int index) throws Exception
        {
            if(index <-1 || index > size -1)
            {
                throw new Exception("参数错误！");
            }
            //说明在头结点之后操作。
            if(index==-1)    //因为第一个数据元素结点的下标是0，那么头结点的下标自然就是-1了。
                return;
            current = head.next;
            int j=0;//循环变量
            while(current != head&&j<index)
            {
                current = current.next;
                j++;
            }

        }

        public void delete(int index) throws Exception {
            // TODO Auto-generated method stub
            //判断链表是否为空
            if(isEmpty())
            {
                throw new Exception("链表为空，无法删除！");
            }
            if(index <0 ||index >size)
            {
                throw new Exception("参数错误！");
            }
            index(index-1);//定位到要操作结点的前一个结点对象。
            current.setNext(current.next.next);
            size--;
        }

        public Object get(int index) throws Exception {
            // TODO Auto-generated method stub
            if(index <-1 || index >size-1)
            {
                throw new Exception("参数非法！");
            }
            index(index);

            return current.getElement();
        }

        public void insert(int index, Object obj) throws Exception {
            // TODO Auto-generated method stub
            if(index <0 ||index >size)
            {
                throw new Exception("参数错误！");
            }
            index(index-1);//定位到要操作结点的前一个结点对象。
            /*current.setNext(new Node(obj,current.next));*/
            size++;
        }

        public boolean isEmpty() {
            // TODO Auto-generated method stub
            return size==0;
        }

        public int size() {
            // TODO Auto-generated method stub
            return this.size;
        }
    }

    //游戏类
    public static class Game {

        //单向循环链表
        CycleLinkList list = new CycleLinkList();
        //总人数
        int num;
        //数到几退出
        int key;

        //游戏初始化方法
        public Game(int num,int key)
        {
            this.num = num;
            this.key = key;
        }

        public void play() throws Exception
        {
            for(int i=0;i<num;i++)
            {
                list.insert(i, i);
            }

            System.out.println("\n-------游戏开始之前---------\n");
            for(int i=0;i<list.size;i++)
            {
                System.out.print(list.get(i)+" ");
            }
            System.out.println("\n-------游戏开始---------\n");
            int iCount=num; //开始等于总人数num
            int j=0; //累加器，计算是否能被key整除。

            Node node = list.head;
            while(iCount!=1)
            {
                if(node.getElement()!=null&& Integer.parseInt(node.getElement().toString())!=-1)
                {
                    j++;
                    if(j%key==0)
                    {
                        node.setElement(-1);
                        iCount--;
                        System.out.println();
                        for(int i=0;i<list.size;i++)
                        {
                            System.out.print(list.get(i)+" ");
                        }
                    }
                }
                node = node.next;
            }
            System.out.println("\n-------游戏结束---------\n");
            for(int i=0;i<list.size;i++)
            {
                System.out.print(list.get(i)+" ");
            }
        }

    }

    public static class Test {

        /**
         * @param args
         */
        public static void main(String[] args) throws Exception {
            // TODO Auto-generated method stub
      /*
      CycleLinkList list = new CycleLinkList();
      for(int i=0;i<10;i++)
      {
         int temp = ((int)(Math.random()*100))%100;
         list.insert(i, temp);
         System.out.print(temp+" ");
      }
      list.delete(4);
      System.out.println("\n------删除第五个元素之后-------");
      for(int i=0;i<list.size;i++)
      {
          System.out.print(list.get(i)+" ");
      }*/

            Game game = new Game(10,3);
            game.play();

        }
    }

}
